﻿#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

class Solution
{
public:
    // 1054. 距离相等的条形码
    vector<int> rearrangeBarcodes(vector<int>& barcodes)
    {
        unordered_map<int, int> hash;
        int MaxVal = 0, MaxCount = 0;
        for (auto x : barcodes)
        {
            if (MaxCount < ++hash[x])
            {
                MaxVal = x;
                MaxCount = hash[x];
            }
        }

        int n = barcodes.size();
        vector<int> ret(n);
        int index = 0;
        for (int i = 0; i < MaxCount; ++i)
        {
            ret[index] = MaxVal;
            index += 2;
        }

        hash.erase(MaxVal);
        for (pair<const int, int>& p : hash)
        {
            for (int i = 0; i < p.second; ++i)
            {
                if (index >= n)
                    index = 1;
                ret[index] = p.first;
                index += 2;
            }
        }
        return ret;
    }

    // 767. 重构字符串
    string reorganizeString(string s)
    {
        int hash[26] = { 0 };
        int MaxCount = 0;
        char MaxChar = ' ';
        for (auto x : s)
        {
            if (MaxCount < ++hash[x - 'a'])
            {
                MaxChar = x;
                MaxCount = hash[x - 'a'];
            }
        }

        int n = s.size();
        if (MaxCount > (n + 1) / 2)
            return "";

        string ret(n, ' ');
        int index = 0;
        for (int i = 0; i < MaxCount; ++i)
        {
            ret[index] = MaxChar;
            index += 2;
        }
        hash[MaxChar - 'a'] = 0;

        for (int i = 0; i < 26; ++i)
        {
            for (int j = 0; j < hash[i]; ++j)
            {
                if (index >= n)
                    index = 1;
                ret[index] = 'a' + i;
                index += 2;
            }
        }
        return ret;
    }
};

int main()
{
    /*vector<int> v{ 1,1,1,2,2,2 };
    vector<int> ret = Solution().rearrangeBarcodes(v);
    for (auto x : ret)
        cout << x << " ";
    cout << endl;*/

    string s = "abb";
    cout << Solution().reorganizeString(s) << endl;

    return 0;
}